#ifndef _TREE_H_
#define _TREE_H_ 1
#include <iostream>
#include <queue>
#include <unordered_map>
#include <vector>

using std::unordered_map;

struct TreeNode {
  public:
    int value;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int val, TreeNode *left_child, TreeNode *right_child) : value(val), left(left_child), right(right_child) {};
    TreeNode(int val) : value(val), left(nullptr), right(nullptr) {};
    TreeNode() : value(0), left(nullptr), right(nullptr) {};
};

class BinaryTree
{
  private:
    TreeNode *create_tree_by_preorder_inorder_help(const std::vector<int> &preorder, const std::vector<int> &inorder, int start_pre, int end_pre, int start_in, int end_in,
                                                   const std::unordered_map<int, int> &value_2_index);
    TreeNode *create_tree_by_inorder_lastorder_help(const std::vector<int> &inorder, const std::vector<int> &lastorder, int start_in, int end_in, int start_last, int end_last,
                                                    const std::unordered_map<int, int> &value_2_index);

  public:
    TreeNode *root;
    BinaryTree(TreeNode *T) : root(T) {};
    BinaryTree() : root(nullptr) {};
    BinaryTree(const std::vector<int> &init_array) { create_binary_tree_by_array(init_array); }
    BinaryTree(const std::vector<int> &order1, const std::vector<int> order2, int method);
    virtual ~BinaryTree();
    void set_root(TreeNode *T) { this->root = T; };
    TreeNode *get_root() { return this->root; };
    int create_binary_tree_by_array(const std::vector<int> &);
    /* 以先序和中序遍历递归创建二叉树 */
    TreeNode *create_binary_tree_preorder_inorder(const std::vector<int> &preorder, const std::vector<int> &inorder);
    /* 以中序和后续遍历递归创建二叉树 */
    TreeNode *create_binary_tree_inorder_lastorder(const std::vector<int> &preorder, const std::vector<int> &inorder);
    void level_order();
    void pre_order(TreeNode *);
    void in_order(TreeNode *);
    void last_order(TreeNode *);
};

class BinarySearchTree final : public BinaryTree
{
  public:
    BinarySearchTree(TreeNode *node) : BinaryTree(node) {}
    BinarySearchTree() : BinaryTree() {}
    BinarySearchTree(const std::vector<int> &order1, const std::vector<int> order2, int method);
    ~BinarySearchTree() { std::cout << "Call ~BinarySearchTree" << std::endl; }
    TreeNode *search_node(int val);
    void insert_node(int val);
    void delete_node(int val);
};

#endif